/**
 * @param {number} n
 * @param {number[][]} roads
 * @return {number}
 */
 var countPaths = function(n, roads) {
  const mod = 1e9+7
  const INF = Number.MAX_SAFE_INTEGER
  const g = new Array(n).fill(0).map(() => new Array(n).fill(INF))
  for(const [u, v, time] of roads){
    g[u][v] = time
    g[v][u] = time
  }
  const distance = new Array(n).fill(INF)
  distance[0] = 0
  const used = new Array(n).fill(false)
  for(let i = 0; i<n; i++){
    let x = -1
    for(let y = 0; y<n; y++){
      if(!used[y] && (x === -1 || distance[y] < distance[x])){
        x = y
      }
    }
    used[x] = true
    for(let y = 0; y<n; y++){
      distance[y] = Math.min(distance[y], distance[x] + g[x][y])
    }
  }
  const min = distance[n-1]
  // 求路线总数
  const dp = new Array(n).fill(0).map(() => new Array(n).fill(0).map(() => new Array(min).fill(0)))
  for(const [u, v, time] of roads){
    dp[u][v][time] = 1
    dp[v][u][time] = 1
  }
  for(let j = 0; j<n; j++){
    if(g[0][j] + g[j][n-1] <= min){
      const sum = g[0][j] + g[j][n-1]
      dp[0][n-1][sum] = (dp[0][n-1][sum] + dp[0][j][g[0][j]] + dp[j][n-1][g[j][n-1]])%mod
    }
  }
  return dp[0][n-1][min]
};